home *** CD-ROM | disk | FTP | other *** search
- *****Listing 1*****
-
- #include <stdio.h>
-
- #define NSTACK 30 /* 2 log2 (max n) */
- typedef unsigned int ARRTYPE; /* type of data to be sorted */
-
- void iqsort( n, arr, indx) /* 1 based arrays */
- unsigned int n; /* sort arr[1..n] */
- ARRTYPE arr[], *indx[]; /* return indx pointers to sorted arr[] */
- {
- static unsigned int stack[NSTACK+1], llim, rlim, iq, i, j;
- int jstack = 1; /* "unsigned int" may be faster... */
- static ARRTYPE *a, *b;
- static int swap;
-
- /* initialize pointers to input order */
- for( i = 1; i <= n; ++i)
- indx[i] = &arr[i];
-
- /* terminate with first pivot element (chosen same as below) */
- indx[n + 1] = indx[((rlim = n) + (llim = 1)) >> 1];
- do
- { /* while any unsorted segments remain */
- while((int)(rlim - llim) > 1 )
- { /* 3 or more elements */
- /* quick sort: split segment into 3 segments */
- /* pick guess of median element to make segments near equal */
- a = indx[iq = ((i = llim) + (j = rlim)) >> 1];
- indx[iq] = indx[i];
- indx[i] = a; /* for left terminator */
- for( ; ; )
- {
- /* search for small element to be moved to left */
- while( *a < *(b = indx[j]))
- --j;
- if(j <= i)
- break;
-
- indx[i] = b;
-
- /* search for large element to be moved to right */
- while( *(b = indx[++i]) < *a )
- ;
- if(i >= j)
- {
- i = j;
- break;
- }
- indx[j--] = b;
- }
-
- indx[i] = a; /* new middle segment, length 1 */
- if( (jstack += 2) > NSTACK )
- printf("\nNSTACK exceeded");
-
- /* work shorter segment next to limit stacking */
- stack[jstack] = (swap = (rlim-i >= i-llim)) ? rlim : (i-1);
- stack[jstack - 1] = swap ? (i+1) : llim;
- rlim = swap ? (i-1) : rlim;
- llim = swap ? llim : (i+1);
- }
-
- /* finish off short segments directly -- optional case for 2 elements */
- if(rlim - llim == 1 && *(a = indx[llim]) > *(b = indx[llim + 1]) )
- {
- indx[llim] = b;
- indx[llim + 1] = a;
- }
-
- /* get next segment to sort from stack */
-
- rlim = stack[jstack--];
- llim = stack[jstack--];
- } while(jstack != -1);
- }
-